home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 090 / cmln0885.arc / NIAL2.LTG < prev    next >
Text File  |  1986-02-27  |  2KB  |  50 lines
  1.  
  2.  
  3. Nial Listing 2
  4.  
  5.  
  6. Sieve of Eratosthenes
  7.  
  8. sieve IS OPERATION N {
  9.   Candidates := rest count N;
  10.   Primes := Null;
  11.   WHILE not empty Candidates DO
  12.     Primes := Primes append first Candidates;
  13.     Candidates := not (Candidates mod first Candidates match 0) 
  14.          sublist Candidates;
  15.   ENDWHILE;
  16.   Primes }
  17.  
  18. Explanation:
  19.  
  20.   count N                     gives array of numerals from 1 through N.
  21.   rest count N                gives array of numerals from 2 through N.
  22.   Primes := Null              initializes array Primes to empty array.
  23.   Candidates mod first Candidates
  24.                               gives array of remainders after dividing
  25.                               elements of Candidates by first element.
  26.   Candidates ... match 0      gives a bitstring true for elements which
  27.                               match 0, false otherwise.
  28.   not ... match 0)            gives bitstring with true changed to false
  29.                               and false to true.
  30.   Candidates := ... sublist Candidates
  31.                               gives an array which is a sublist of
  32.                               Candidates consisting of the elements
  33.                               of Candidates which correspond to the
  34.                               true bits in the bitstring, and assigns it
  35.                               to Candidates.
  36.   Primes := Primes append first Candidates
  37.                               appends the first element of the array
  38.                               Candidates to the array Primes.
  39.  
  40.     Thσ WHIL┼ loo≡ start≤ witΦ aε arra∙ calleΣ Candidate≤, ì
  41. consistinτ oµ thσ numeral≤ froφ ▓ througΦ N« I⌠ firs⌠ append≤ ▓ ì
  42. t∩ thσ arra∙ Primes¼ then replace≤ Candidate≤ witΦ aε arra∙ ì
  43. consistinτ oµ thσ element≤ oµ thσ previous arra∙ no⌠ divisiblσ b∙ ì
  44. thσ firs⌠ elemen⌠ oµ tha⌠ previou≤ array¼ initiall∙ 2, anΣ append≤ ì
  45. thσ firs⌠ elemen⌠ oµ tha⌠ ne≈ arra∙ t∩ thσ arra∙ Primes« Thσ ì
  46. loop terminate≤ wheε n∩ morσ element≤ remaiε iε thσ arra∙ ì
  47. Candidates«  Oε ß Fortunσ 32:1╢ witΦ ▒M┬ oµ RA═ anΣ onσ use≥ ì
  48. loggeΣ on¼ thσ timσ fo≥ ╬ ╜ 100░ wa≤ 5▒ sec.
  49.  
  50.